#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    auto build = [&](auto&& build, int begin, int end, int& u)->TreeNode* {
        if (begin > end) return nullptr;

        auto node = new TreeNode(preorder[u]);
        int i;
        for (i = begin; i <= end; i++)
            if (preorder[u] == inorder[i])
                break;
        u++;
        node->left = build(build, begin, i - 1, u);
        node->right = build(build, i + 1, end, u);

        return node;
    };
    int i = 0;
    return build(build, 0, preorder.size() - 1, i);
}